The present invention relates to social networks. More specifically, the present invention relates to methods and apparatus for providing high-performance relationship reporting between users in a social network.
Conventional methods for determining the relationships between a user and other users in a network of users have included the use of a relational database to store, determine and provide the relationships.
The primary difficulty with such approaches is the exponential growth of size of a social network. For example, if a first user knows “n” (e.g. 100) second users on the social network, and each of the “n” (e.g. 100) second users knows “n” (e.g. 100) unique third users, etc., the first user may have n^2 (e.g. 100^2=1,000) users in their social network that are within two “degrees of separation” away. Additionally, the first user may have n^3 (e.g. 100^3=100,000) users in their social network that are within three “degrees of separation” away. Accordingly, when a social network has a large number of users, the number of computations required to determine a social map increases dramatically (e.g. exponentially). As a result, performing social network calculations on large social networks cannot be done in real-time, as such a system would take too long to compute whenever there is a change in the social network.
The inventors of the present invention believe that relational databases alone are not well-suited to perform social network calculations because of this exponential growth in size of a user's social map when a small number of first degree (direct) relationships are added to the whole social network.
One attempt to address this exponential computation growth has been to perform such computations at night time, at off-peak hours, or other specified batch time. The computations of users' social map would then be stored in memory for use at a later time, until the next batch time. Between computations, the cached computation data would then provided to the user when requested. Drawbacks to this approach included that when the user requested their social map, the user network, the user would be provided with a copy of the data previously cached at batch time. Further, any changes initiated by the user before the next batch process, would not be visible until the next batch time. Additional drawbacks included that caching the relationship data for a large number of users would be prohibitively hardware expensive.
In light of the above, what is required are improved methods and apparatus that address the issues above.